﻿#include <string>
#include <iostream>

using std::string;
using std::cout;
using std::endl;
/*
1.1 旋转字符串
	题目描述：
		给定一个字符串，要求把字符串前面的若干个字符移动到到字符串的尾部，如字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部，
	使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度n的字符串操作的时间复杂度为O(n)，空间复杂度为O(1).
*/

/*
解法：三步反转法
	将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把所有的字符反转（如，X="abc"，那么X^T="cba"），
	那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字符串的反转问题
*/

//reverse a charArray from begin to end.
void ReverseString(char *s, int begin, int end){
	while (begin<end)
	{
		char temp = s[begin];
		s[begin++] = s[end];
		s[end--] = temp;
	}
	cout << "["<<begin<<"..."<<end<<"]^T : " << s << endl;
}

//move the n characters which in front of the charArray to the tail.
//@param	len: charArray.length		n: 
void LeftRotateString(char *s, int len, int n){
	n %= len;
	ReverseString(s, 0, n - 1);		//reverse [0...n-1],that is to say: X^T
	ReverseString(s, n, len - 1);		//reverse [n...len-1],that is to say: Y^T
	ReverseString(s, 0, len - 1);		//reverse [0...len-1],that is to say: (X^TY^T)^T	
}
